This invention relates generally to granting mutual exclusion to processors during memory accesses, and more particularly to granting mutual exclusion to processors in a remote-write globally ordered network of processors.
There has been much work in implementing fast mutual exclusion on computer systems that support a variety of capabilities in hardware. Most work has focused on a network of multi-processors where all processors can access a shared memory via some interconnect. The processors"" view of the shared memory is usually kept consistent according to a particular memory consistency model, such as sequential consistency. For example, given sequential consistency, a number of algorithms are known, such as Decker""s algorithm, Lamport""s Bakery algorithm, Peterson""s algorithm, and Lamport""s 1-bit algorithm. Typically, these algorithms obtain mutual exclusion with respect to a named object known as a lock, so xe2x80x9cacquiring a lockxe2x80x9d expresses the concept of obtaining mutual exclusion for a process.
These algorithms have varying properties, such as whether they generalize easily to more than two processes, whether processes can get xe2x80x9cstarvedxe2x80x9d, how many reads and writes they do in the common case, and so forth. Please see, E. W. Dijkstra xe2x80x9cSolution of a problem in concurrent programming control,xe2x80x9d Communications of the ACM, Vol. 8, No. 9, p. 569, September 1965; Leslie Lamport xe2x80x9cA new solution of Dijkstra""s concurrent programming problemxe2x80x9d, Communications of the ACMxe2x80x9d, Vol. 17, No. 8, pp. 86-88, August 1974; Leslie Lamport xe2x80x9cThe Mutual Exclusion Problem: Part IIxe2x80x94Statement and Solutionsxe2x80x9d, Journal of the ACM, Vol. 33, No., 2, pp. 327-346, April 1986; and G. L. Peterson xe2x80x9cA new solution to Lamport""s concurrent programming problemxe2x80x9d ACM Transactions on Programming Languages and Systems, Vol. 5, No. 1, pp. 56-65, January 1983.
U.S. Pat. No. 5,553,298 xe2x80x9cMethod and apparatus for mutual exclusion in self-directed distributed systemsxe2x80x9d issued to Merryman on Sep. 3, 1996 describes a method of mutual exclusion between processes connected by a network. There, mutual exclusion is achieved by having the processors broadcast their interest in obtaining a lock. However, the method uses a simple back-off system where processors keep backing off until only one process is expressing an interest. The method uses time constants in the network to determine how long a process must wait after expressing an interest before it can be sure that it has the lock. The problem with that method is that in modem networks, time xe2x80x9cconstantsxe2x80x9d may change over time.
In shared memory systems, lock contention occurs when more than one process expresses an interest to acquire a particular lock at the same time. In a simple approach, this problem can be overcome by having a process write a value into an element of shared memory array to indicate that the process wants to acquire a lock. If there is no contention, then the process immediately gets the lock with just the single write access. However, when there is contention, all contending processes xe2x80x9cback offxe2x80x9d by zeroing their request from the corresponding elements of the array, and waiting a semi-random, and ever-increasing amount of time, and then trying again later until there is no contention. When there are many processes contending for the same lock, this back-off strategy can be very expensive, because processes can have repeated conflicts until they back-off for long amounts of time.
Therefore, there is a need for a mutual exclusion method that can acquire a lock with a single write access when there is no contention, yet the method would operate efficiently without back-off when there is contention. In addition, the method should grant locks to processes in a first-come, first-served xe2x80x9cfairxe2x80x9d manner that does not lead to xe2x80x9cstarvationxe2x80x9d of individual processes.
The invention provides a method for acquiring a lock in a network of processors with globally ordered remote-writes. A process requesting a lock changes an associated ticket number from zero to one. Next, the process determines if every other process attempting to acquire the lock has a ticket number of zero. If true, the request for the lock is immediately granted. Otherwise, if false, the process changes its ticket number to a value greater than that of every other process, and the process waits until its ticket number is the lowest non-zero ticket number, in which case the lock is granted with mutual exclusion.
In one aspect of the invention, ticket numbers are integer values in the range from zero to a predetermined maximum integer value. Ticket numbers are assigned in order of lock requests.
In another aspect of the invention, the ticket number of the process is set to zero when the next available lowest ticket number is greater than the predetermined maximum integer value. In this case, the process restarts the process of acquiring the lock when the ticket numbers of all other processes requesting the lock are less than the predetermined maximum ticket number.